package star.动态规划.礼物的最大价值;

public class MaxValue {
    public static void main(String[] args) {

    }
    public int maxValue(int[][] grid) {
        for (int i = 1; i < grid[0].length; i++) {
            grid[0][i] = grid[0][i] + grid[0][i-1];
        }
        for (int i = 1; i < grid.length; i++) {
            grid[i][0] = grid[i][0] + grid[i-1][0];
        }
        for (int i = 1; i < grid[0].length; i++) {
            for (int j = 1; j < grid.length; j++) {
                grid[j][i] = grid[j-1][i] > grid[j][i-1] ? grid[j-1][i]+grid[j][i] : grid[j][i-1]+grid[j][i];
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}
